Removing uneeded file.
[andmenj-acm.git] / UVa / 10065 - Useless tile packers / 10065.2.cpp
blob0c8e9be27566181cc895f8eb553a158a23c3d592
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <iterator>
5 #include <cmath>
7 using namespace std;
9 struct point{
10 int x,y;
11 point() {}
12 point(int X, int Y) : x(X), y(Y) {}
15 point pivot;
17 ostream& operator<< (ostream& out, const point& c)
19 out << "(" << c.x << "," << c.y << ")";
20 return out;
23 //P es un polígono ordenado anticlockwise.
24 //Si es clockwise, retorna el area negativa.
25 //Si no esta ordenado retorna pura mierda.
26 //P[0] != P[n-1]
27 double area(const vector<point> &p){
28 double r = 0.0;
29 for (int i=0; i<p.size(); ++i){
30 int j = (i+1) % p.size();
31 r += p[i].x*p[j].y - p[j].x*p[i].y;
33 return r/2.0;
36 //retorna si c esta a la izquierda de el segmento AB
37 inline int cross(const point &a, const point &b, const point &c){
38 return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
41 //Self < that si esta a la derecha del segmento Pivot-That
42 bool angleCmp(const point &self, const point &that){
43 return( cross(pivot, that, self) < 0 );
46 inline int distsqr(const point &a, const point &b){
47 return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
50 //vector p tiene los puntos ordenados anticlockwise
51 vector<point> graham(vector<point> p){
52 pivot = p[0];
53 sort(p.begin(), p.end(), angleCmp);
54 //Ordenar por ángulo y eliminar repetidos.
55 //Si varios puntos tienen el mismo angulo se borran todos excepto el que esté más lejos
56 for (int i=1; i<p.size()-1; ++i){
57 if (cross(p[0], p[i], p[i+1]) == 0){ //Si son colineales...
58 if (distsqr(p[0], p[i]) < distsqr(p[0], p[i+1])){ //Borrar el mas cercano
59 p.erase(p.begin() + i);
60 }else{
61 p.erase(p.begin() + i + 1);
63 i--;
67 vector<point> chull(p.begin(), p.begin()+3);
69 //Ahora sí!!!
70 for (int i=3; i<p.size(); ++i){
71 while ( chull.size() >= 2 && cross(chull[chull.size()-2], chull[chull.size()-1], p[i]) < 0){
72 chull.erase(chull.end() - 1);
74 chull.push_back(p[i]);
77 return chull;
80 int main(){
81 int n;
82 int tileNo = 1;
83 while (cin >> n && n){
84 vector<point> p;
85 point min(10000, 10000);
86 int minPos;
87 for (int i=0; i<n; ++i){
88 int x, y;
89 cin >> x >> y;
90 p.push_back(point(x,y));
91 if (y < min.y || (y == min.y && x < min.x )){
92 min = point(x,y);
93 minPos = i;
96 double tileArea = fabs(area(p));
98 //Destruye el orden cw|ccw poligono, pero hay que hacerlo por que Graham necesita el pivote en p[0]
99 swap(p[0], p[minPos]);
100 pivot = p[0];
101 double chullArea = fabs(area(graham(p)));
103 printf("Tile #%d\n", tileNo++);
104 printf("Wasted Space = %.2f \%\n\n", (chullArea - tileArea) * 100.0 / chullArea);
107 return 0;